package com.atguigu.dac;

/**
 * 分治法: 分而治之
 * 步骤: 分解->解决->合并
 * 汉诺塔问题: 三个塔A、B、C,塔A从小到大依次存放若干个圆盘,如何将A的圆盘移动到C，圆盘的要求是大的圆盘不能下小圆盘的上面
 * 解决思路: 将上面的看成一个盘，最后一块看成一个盘
 * 解决步骤：
 * 1.如果只有一个盘  A->C
 * 2.如果盘数>=2情况，可以看成两个盘，1：最下面的盘，2：上面的盘
 * 1) 先把最上面的盘移动B A->B
 * 2) 把最下面的盘移动到C A->C
 * 3) 把B塔的所有盘移动到C B->C
 *
 * @author dataexa
 * @Date 2024/1/31
 */
public class Hannuotower {
    public static void main(String[] args) {
        hanoiTower(2, 'A', 'B', 'C');
    }

    //使用分治实现汉诺塔
    public static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println("第1个盘从: " + a + "->" + c);
        } else {
            // * 1) 先把最上面的盘移动B A->B
            hanoiTower(num - 1, a, c, b);
            // * 2) 把最下面的盘移动到C A->C
            System.out.println("第" + num + "个盘从: " + a + "->" + c);
            // * 3) 把B塔的所有盘移动到C B->C
            hanoiTower(num - 1, b, a, c);
        }
    }
}
